package com.company.剑指offer每日刷题.普通版;

import java.util.HashMap;
import java.util.Map;

/**
 * 剑指 Offer 35. 复杂链表的复制
 * 请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，
 * 每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。
 * */
public class copyRandomList {
    class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }
    /**
     * 方法1：回溯 + 哈希表
     * 难点：因为按照单链表的复制方式而言，是依次遍历并且复制这些节点。但是这里节点中加入了一个新的随机指针。这就导致了我们复制一个节点的时候，
     *      它所指向的随机节点可能还不存在。
     * 思路：1.在遍历并复制这些节点的时候呢，先复制这个节点本身，然后复制这个节点的后缀节点和随机节点
     *      2.随机节点和后缀节点都被复制并指定了。当前节点的复制才算完成。
     *      3.后缀节点和随机节点的复制可以通过递归的方式去复制。
     *      4.为了避免每一个节点不被重复复制，我们通过哈希表来存储这些节点。key是head上的节点，value是新链表上对应的节点。
     * */
    Map<Node,Node> cacheNodes = new HashMap<>();
    public Node copyRandomList(Node head) {
        //结束条件
        if(head == null){
            return null;
        }
        if(!cacheNodes.containsKey(head)){
            Node newNode = new Node(head.val);
            cacheNodes.put(head,newNode);
            newNode.next = copyRandomList(head.next);
            newNode.random = copyRandomList(head.random);
            return newNode;
        }else{
            return cacheNodes.get(head);
        }
    }
}
